package org.xsk.structure.tree;

public class Tree {

    private Node root;

    public Node find(int key){
        Node current = root;
 
        while(current.person.iData != key){
            if(key < current.person.iData){
                current = current.leftChild;
            }else{
                current = current.rightChild;
            }
            if (current == null) {
                return null;
            }
        }
        return current;
    };

    public void insert(int key,double dd){
        Node node = new Node();
        Person person = new Person();
        person.fData = key;
        person.fData = dd;
        node.person = person;
        if (root == null) {
            root = node;
        } else {
            Node current = root;
            Node parent;
            while (true) {
                parent = current;
                if (key < current.person.iData) {
                    current = current.leftChild;
                    if (current == null) {
                        parent.leftChild = node;
                        return;
                    }
                } else {
                    current = current.rightChild;
                    if (current == null) {
                        parent.rightChild = node;
                        return;
                    }
                    
                }
            }
        }

    }

    public boolean delete(int key){

        Node current = root;
        Node parent = root;
        boolean isLeftChild = true;

        while (current.person.iData != key) {
            parent = current;
            if (key < current.person.iData) {
                isLeftChild = true;
                current = current.leftChild;
            } else {
                isLeftChild = false;
                current = current.rightChild;
            }
            if (current == null) {
                return false;
            }
        }

        if (current.leftChild == null && current.rightChild == null) {
            if (current == root) {
                root = null;
            } else if (isLeftChild) {
                parent.leftChild = null;
            } else {
                parent.rightChild = null;
            }
        }else if(current.rightChild == null){
            if (current == root) {
                root = current.leftChild;
            }else if (isLeftChild) {
                parent.leftChild = current.leftChild;
            } else {
                parent.rightChild = current.leftChild;
            }
        }else if (current.leftChild == null) {
            if (current == root) {
                root = current.rightChild;
            } else if (isLeftChild) {
                parent.leftChild = current.rightChild;
            } else {
                parent.rightChild = current.rightChild;
            }
        }
        return false;
    }

    public void getSuccessor(Node delNode){

        Node parentNode = delNode;
        Node successorNode = delNode;
        Node current = delNode.rightChild;
        while (current != null) {
            parentNode = successorNode;
            successorNode = current;
            current = current.leftChild;
        }

        if (successorNode != delNode.rightChild) {
            parentNode.leftChild = successorNode.rightChild;
            
        }
        
    }

    public void loop(){
        inOrder(root);
    }

    private void inOrder(Node nodeRoot){
        if (nodeRoot != null) {
            inOrder(nodeRoot.leftChild);
            System.out.println(nodeRoot.person.iData + "");
            inOrder(nodeRoot.rightChild);
        }

    }

}
